package com.hdu.hot100.oneDimensionalDp;

import java.util.Arrays;

public class lc279 {
    class Solution {
        public int numSquares(int n)
        {
            int[] dp = new int[n + 1];
            int max = Integer.MAX_VALUE;
            Arrays.fill(dp, max);
            dp[0] = 0;
            for (int i = 1; i * i <= n; i++)
            {
                int curObj = i * i;
                for (int j = curObj; j <= n; j++)
                {
                    if (dp[j - curObj] != max)
                    {
                        dp[j] = Math.min(dp[j], dp[j - curObj] + 1);
                    }
                }
            }
            return dp[n];
        }
    }
}
